package org.liaohailong.helloworld.practice;

import android.os.Build;

import androidx.annotation.RequiresApi;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;

/**
 * Author: liaohailong
 * Date: 2021/6/4
 * Time: 21:26
 * Description: 初级算法 - 数组练习
 **/
public class ArrayPractice {

    // LC 删除排序数组中的重复项
    public int removeDuplicates(int[] nums) {
        int slow = 0;
        for (int fast = 1; fast < nums.length; fast++) {
            if (nums[fast] != nums[slow]) {
                nums[slow + 1] = nums[fast];
                slow++;
            }
        }
        return slow + 1;
    }

    // LC 买卖股票的最佳时机 II
    public int maxProfit(int[] prices) {
        // [7,1,5,3,6,4] = 7
        // [7,6,4,3,1] = 0
        // [1,2,3,4,5] = 4

        int minPrice = prices[0];
        int profit = 0;
        for (int i = 1; i < prices.length; i++) {
            int price = prices[i];
            // 今天比昨天贵，能赚钱，尝试赚钱
            if (minPrice < price) {
                profit += (price - minPrice);
                minPrice = price;
            } else {
                // 今天跌了，昨天就该卖了
                minPrice = price;
            }
        }

        return profit;
    }

    // LC 旋转数组 时间复杂度：O(n) 空间复杂度：O(n)
//    public void rotate(int[] nums, int k) {
//        k %= nums.length;
//        k = nums.length - k; // 后面数第k个
//
//        // [k,length-1] -> 最前面
//        int[] result = new int[nums.length];
//        int pos = -1;
//        for (int i = k; i < nums.length; i++) {
//            pos++;
//            result[pos] = nums[i];
//        }
//        for (int i = 0; i < k; i++) {
//            pos++;
//            result[pos] = nums[i];
//        }
//        System.arraycopy(result, 0, nums, 0, nums.length);
//    }

    // LC 旋转数组 时间复杂度：O(n) 空间复杂度：O(k)
//    public void rotate(int[] nums, int k) {
//        k %= nums.length;
//        int h = k;
//        k = nums.length - k;
//        // swap
//        int[] head = new int[h];
//        int pos = -1;
//        for (int i = k; i < nums.length; i++) {
//            pos++;
//            head[pos] = nums[i];
//        }
//        // 整体右偏
//        System.arraycopy(nums, 0, nums, h, k);
//        // 补充head
//        System.arraycopy(head, 0, nums, 0, head.length);
//    }

    // LC 旋转数组  时间复杂度：O(n) 空间复杂度：O(1)
    public void rotate(int[] nums, int k) {
        k %= nums.length;
        reserve(nums, 0, nums.length - 1);
        reserve(nums, 0, k - 1);
        reserve(nums, k, nums.length - 1);
    }

    private void reserve(int[] nums, int i, int j) {
        while (i < j) {
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
            i++;
            j--;
        }
    }

    // LC 存在重复元素
    public boolean containsDuplicate(int[] nums) {
//        HashSet<Integer> cache = new HashSet<>();
//        for (int num : nums) {
//            if(cache.contains(num)) return true;
//            else cache.add(num);
//        }
//        return false;

        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 1; i++) {
            if (nums[i] == nums[i + 1]) return true;
        }
        return false;

//        HashSet<Integer> cache = new HashSet<>();
//        for (int num : nums) {
//            cache.add(num);
//        }
//        return cache.size() != nums.length;
    }

    // LC 只出现一次的数字
    public int singleNumber(int[] nums) {
        int t = nums[0];
        for (int i = 1; i < nums.length; i++) {
            t ^= nums[i];
        }
        return t;
    }

    // LC 两个数组的交集 II - 排序比较 空间复杂度O(1)
//    public int[] intersect(int[] nums1, int[] nums2) {
//        Arrays.sort(nums1);
//        Arrays.sort(nums2);
//        int[] shorter;
//        int[] longer;
//        if (nums1.length > nums2.length) {
//            shorter = nums2;
//            longer = nums1;
//        } else {
//            shorter = nums1;
//            longer = nums2;
//        }
//
//        int min = shorter[0];
//        int minInLonger = -1;
//        for (int i = 0; i < longer.length; i++) {
//            if (longer[i] >= min) {
//                minInLonger = i;
//                break;
//            }
//        }
//        if (minInLonger == -1) return new int[0];
//
//        // result as linked list
//        ArrayList<Integer> list = new ArrayList<>();
//        // i = shorter begin
//        // j = longer begin
//        int i = 0, j = minInLonger;
//        while (i < shorter.length && j < longer.length) {
//            if (shorter[i] == longer[j]) {
//                list.add(shorter[i]);
//                i++;
//                j++;
//            } else {
//                if (shorter[i] < longer[j]) {
//                    i++;
//                } else {
//                    j++;
//                }
//            }
//        }
//        int[] result = new int[list.size()];
//        int pos = -1;
//        for (Integer integer : list) {
//            pos++;
//            result[pos] = integer;
//        }
//        return result;
//    }

    // LC 两个数组的交集 II - 缓存计数 空间复杂度O(n)
    @RequiresApi(api = Build.VERSION_CODES.N)
    public int[] intersect(int[] nums1, int[] nums2) {
        HashMap<Integer, Integer> cache = new HashMap<>();
        for (int val : nums1) {
            cache.put(val, cache.getOrDefault(val, 0) + 1);
        }
        ArrayList<Integer> list = new ArrayList<>();
        for (int val : nums2) {
            Integer count = cache.get(val);
            if (count != null && count > 0) {
                int newCount = count - 1;
                cache.put(val, newCount);
                list.add(val);
            }
        }
        int[] result = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            Integer val = list.get(i);
            result[i] = val;
        }
        return result;
    }

    // LC 加一
    public int[] plusOne(int[] digits) {
        int extra = 0;
        int pos = digits.length - 1;
        while (pos >= 0) {
            int curr = digits[pos];
            if (pos == digits.length - 1)
                curr++;
            else if (extra > 0) {
                curr++;
            }
            extra = curr / 10;
            int val = curr % 10;
            digits[pos] = val;
            pos--;
            if (extra <= 0) break;
        }
        // last but not least
        if (extra > 0) {
            int[] result = new int[digits.length + 1];
            System.arraycopy(digits, 0, result, 1, digits.length);
            result[0] = extra;
            digits = result;
        }

        return digits;
    }

    // LC 移动零
    public void moveZeroes(int[] nums) {
        int slow = 0;
        for (int fast = 0; fast < nums.length; fast++) {
            if (nums[fast] != 0) {
                nums[slow] = nums[fast];
                slow++;
            }
        }
        Arrays.fill(nums, slow, nums.length, 0);
    }

    // LC 两数之和
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> cache = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int num = nums[i];
            int find = target - num;
            Integer index = cache.get(find);
            if (index != null) return new int[]{i, index};
            else cache.put(nums[i], i);
        }
        return new int[]{0, 0};
    }

    // LC 有效的数独
//    public boolean isValidSudoku(char[][] board) {
//        int N = 9;
//        HashSet<Character> cache = new HashSet<>();
//        // 检查每列是否存在重复
//        for (int i = 0; i < N; i++) {
//            cache.clear();
//            for (int j = 0; j < N; j++) {
//                char c = board[j][i];
//                if (c == '.') continue;
//                if (cache.contains(c)) {
//                    return false;
//                } else cache.add(c);
//            }
//        }
//        // 检查每行是否存在重复
//        for (int i = 0; i < N; i++) {
//            cache.clear();
//            for (int j = 0; j < N; j++) {
//                char c = board[i][j];
//                if (c == '.') continue;
//                if (cache.contains(c)) {
//                    return false;
//                } else cache.add(c);
//            }
//        }
//        // 检查3*3矩阵有没有重复数字
//        int rowFrom;
//        int rowTo;
//        int columnFrom;
//        int columnTo;
//        for (int i = 0; i < 3; i++) {
//            rowFrom = i * 3;
//            rowTo = rowFrom + 3;
//            for (int j = 0; j < 3; j++) {
//                columnFrom = j * 3;
//                columnTo = columnFrom + 3;
//                boolean valid = _isValidSudoku(board, rowFrom, rowTo, columnFrom, columnTo, cache);
//                if (!valid) return false;
//            }
//        }
//        return true;
//    }

    //    public boolean _isValidSudoku(char[][] board, int rowFrom, int rowTo,
//                                  int columnFrom, int columnTo,
//                                  HashSet<Character> cache) {
//        cache.clear();
//        for (int i = rowFrom; i < rowTo; i++) {
//            for (int j = columnFrom; j < columnTo; j++) {
//                char c = board[i][j];
//                if (c == '.') continue;
//                if (cache.contains(c)) {
//                    return false;
//                } else cache.add(c);
//            }
//        }
//        return true;
//    }

    // LC 有效的数独
    public boolean isValidSudoku(char[][] board) {
        // 所有行
        int[][] row = new int[9][9];
        // 所有列
        int[][] column = new int[9][9];
        // 所有单元格
        int[][] ceil = new int[9][9];

        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] == '.') continue;
                int num = board[i][j] - '0' - 1;
                // k 表示在第几个单元格
                int k = i / 3 * 3 + j / 3;

                if (ceil[k][num] != 0) return false; // 单元格里面有了
                if (row[i][num] != 0) return false; // 行有了
                if (column[j][num] != 0) return false; // 列有了
                ceil[k][num] = row[i][num] = column[j][num] = 1; // 记录
            }
        }
        return true;
    }

    // LC 旋转图像
//    public void rotate(int[][] matrix) {
//        int N = matrix.length;
//
//        // 按照左上右下对角线镜像
//        for (int i = 0; i < N; i++) {
//            for (int j = i; j < N; j++) {
//                int temp = matrix[i][j];
//                matrix[i][j] = matrix[j][i];
//                matrix[j][i] = temp;
//            }
//        }
//
//        // 水平镜像
//        for (int[] row : matrix) {
//            int left = 0;
//            int right = row.length - 1;
//            while (left < right) {
//                int temp = row[left];
//                row[left] = row[right];
//                row[right] = temp;
//                left++;
//                right--;
//            }
//        }
//    }

    // LC 旋转图像
    public void rotate(int[][] matrix) {
        int length = matrix.length;
        // 维度
        for (int i = 0; i < length / 2; i++) {
            for (int j = i; j < length - i - 1; j++) {
                int temp = matrix[i][j]; // 左上
                int m = length - j - 1; // 下一列
                int n = length - i - 1; // 下一行
                matrix[i][j] = matrix[m][i];
                matrix[m][i] = matrix[n][m];
                matrix[n][m] = matrix[j][n];
                matrix[j][n] = temp;
            }
        }
//        //因为是对称的，只需要计算循环前半行即可
//        for (int i = 0; i < length / 2; i++)
//            for (int j = i; j < length - i - 1; j++) {
//                int temp = matrix[i][j];
//                int m = length - j - 1;
//                int n = length - i - 1;
//                matrix[i][j] = matrix[m][i];
//                matrix[m][i] = matrix[n][m];
//                matrix[n][m] = matrix[j][n];
//                matrix[j][n] = temp;
//            }
    }

}
